#include <bits/stdc++.h>
using namespace std;

/*
2410. 运动员和训练师的最大匹配数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的 训练能力值 。

如果第 i 名运动员的能力值 小于等于 第 j 名训练师的能力值，那么第 i 名运动员可以 匹配 第 j 名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。

请你返回满足上述要求 players 和 trainers 的 最大 匹配数。

 

示例 1：

输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：
- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
可以证明 2 是可以形成的最大匹配数。
示例 2：

输入：players = [1,1,1], trainers = [10]
输出：1
解释：
训练师可以匹配所有 3 个运动员
每个运动员至多只能匹配一个训练师，所以最大答案是 1 。
 

提示：

1 <= players.length, trainers.length <= 105
1 <= players[i], trainers[j] <= 109
*/

// 法一
class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        // 分别排序 双指针来匹配
        // 双指针指向player和trainer的起点
        sort(players.begin(), players.end());
        sort(trainers.begin(), trainers.end());

        // 分别遍历 匹配计数
        int i = 0, j = 0, count = 0;
        int n = players.size(), m = trainers.size();

        while (i < n && j < m) {
            // 当前的运动员匹配当前训练师
            if (players[i] <= trainers[j]) {
                count++;
                i++; // 成功的情况就是运动员和训练师都移动
                j++;
            } else
                j++; //   尝试新的训练师
        }
        return count;
    }
};

// 法二
class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        sort(players.begin(),players.end());
        sort(trainers.begin(),trainers.end());
        int temp = 0,ans = 0,i = 0;
        int n = trainers.size(),m=players.size();
        while(temp < n && i < m){
            if(players[i]>trainers[temp]){
                temp++;
            }
            else{
                ans++;
                i++;
                temp++;
            }         
        }
        return ans;
    }
};

// 法三
class Solution {
public:
    int matchPlayersAndTrainers(std::vector<int>& players, std::vector<int>& trainers) {
		// 对运动员和训练师的能力值进行排序
        std::sort(players.begin(), players.end());
        std::sort(trainers.begin(), trainers.end());
        
        int n = players.size(), m = trainers.size();
        int j = 0; // 训练师指针
        
        for (int i = 0; i < n; ++i) {
            // 找到第一个能匹配当前运动员的训练师
            while (j < m && trainers[j] < players[i]) {
                ++j;
            }
            if (j == m) { // 没有可用训练师了
                return i;
            }
            ++j; // 匹配当前训练师，指针后移
        }
        
        return n; // 所有运动员都匹配到了训练师
    }
};